package demo.letcode;

import java.util.ArrayList;
import java.util.List;

/**
 * 给你一个无重复元素的整数数组candidates和一个目标整数target，找出candidates中可以使用数字和为目标数target的所有不同组合，
 * 并以列表形式返回。你可以按任意顺序返回这些组合。candidates中的同一个数字可以无限制重复被选取。如果至少一个数字的被选数量不同，
 * 则两种组合是不同的
 * 输入：candidates=[2,3,6,7] target=[7]
 * 输出：[[2,2,3],[7]]
 * 解释：2+2+3=7
 */
public class _回溯算法 {

    public static void main(String[] args) {
        int[] a ={2,3,6,7};
        System.out.println(combinationSum(a,7));
    }

    public static List<List<Integer>> combinationSum(int[] candidates, int target) {
        List<List<Integer>> res = new ArrayList<>();
        backTrace(res, new ArrayList<>(), candidates, target, 0);
        return res;
    }

    /**
     * 回溯算法
     *
     * @param res        返回的结果集
     * @param path       路径上的节点
     * @param candidates 源数据
     * @param target     target
     * @param start      起始位置
     */
    private static void backTrace(List<List<Integer>> res, List<Integer> path, int[] candidates, int target, int start) {
        // 因为数组中元素都是正数
        if (target <= 0) {
            if (target == 0) { // 找到一组解就保存下来
                res.add(new ArrayList<>(path));
            }
            return;
        }
        // candidates=[2,3,6,7] target=[7]
        // 因为不能要重复的，所以循环的起始位置不是0
        for (int i = start; i < candidates.length; i++) {
            path.add(candidates[i]);
            backTrace(res, path, candidates, target - candidates[i], i);
            // 递归往回走要撤销选择？？
            // 即当最下面的叶子节点不满足时往回
            path.remove(path.size() - 1);
        }
    }
}
